package com.hyb.algorithm.data.struct.dp;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author: huyanbing
 * @Date: 2021/8/11 7:45 下午
 *
 * https://leetcode-cn.com/problems/n-queens/
 */
/// Basic Recursive
/// Time Complexity: O(n^n)
/// Space Complexity: O(n)
public class SolveNQueens {


    private boolean[] col;

    //状态转移
    private boolean[] dia1;
    private boolean[] dia2;
    private ArrayList<List<String>> res;


    public List<List<String>> solveNQueens(int n) {

        res=new ArrayList<>();
        col=new boolean[n];


        //状态转移
        dia1=new boolean[2*n-1];
        dia2=new boolean[2*n-1];


        LinkedList<Integer> row=new LinkedList<>();

        putQueen(n,0,row);

        return res;
    }

    private void putQueen(int n,int index,LinkedList<Integer> row){

        if(index==n){
            res.add(generateBoard(n,row));
            return;
        }

        for(int i=0;i<n;i++){
            if(!col[i]&&!dia1[index+i]&&!dia2[index-i+n-1]){
                row.addLast(i);
                col[i]=true;
                dia1[index+i]=true;
                dia2[index-i+n-1]=true;
                putQueen(n,index+1,row);

                col[i]=false;
                dia1[index+i]=false;
                dia2[index-i+n-1]=false;
                row.removeLast();
            }
        }

        return;


    }


    private List<String> generateBoard(int n,LinkedList<Integer> row){

        ArrayList<String> board=new ArrayList<>();

        for(int i=0;i<n;i++){
            char[] charArray=new char[n];
            Arrays.fill(charArray,'.');
            charArray[row.get(i)]='Q';
            board.add(new String(charArray));
        }
        return board;
    }

    private static void printBoard(List<String> board){
        for(String s: board) {
            System.out.println(s);
        }
        System.out.println();
    }

    public static void main(String[] args) {

        int n = 4;

        SolveNQueens solveNQueens=new SolveNQueens();
        List<List<String>> res = solveNQueens.solveNQueens(n);
        for(List<String> board: res) {
            printBoard(board);
        }
    }

}
